iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 25
0
自我挑戰組

計算機概論X30天系列 第 25

Day25:[離散數學]威爾斯定理——一個很沒用檢驗質數的方法

  • 分享至 

  • xImage
  •  

閱讀前,建議可以參考Day1:閱讀指南&為何選擇這個題目?

▌挑戰簡介

  • 題目:計算機概論X30天

  • 挑戰內容:連續30天紀錄計算機概論、離散數學、演算法、資料結構等課程,還有自己學習程式的心得體悟。

  • 本篇性質:

    • 純粹學習內容的紀錄,不會有太嚴謹或是流暢的說明,看不懂不要難過,真不是你的智商有問題
    • 威爾斯定理(Wilson's theorem)蠻沒用的,不認識也罷,我純粹就是紀錄一下。

▌威爾斯定理Wilson's theorem

威爾斯定理簡單就是再說

如果 n 是質數,那麼下式必成立
(n-1)!= -1 mod n

比如說

如果n=3
(3-1)! = -1 mod3
2X1 = -1 mod 3(喔!對耶)

▌一個很沒用檢驗質數的方法

那這可以幹嘛呢?

(n-1)!= -1 mod n可以用來檢驗質數。

比如說,如果想知道X是不是質數,那把X放進去威爾斯公式看看就知道了。

但..老實說,這個方法其實很沒用

因為當X很大很大的時候,(x-1)!一定是爆炸大(誰會想算啊)

比如說想知道19291220320323是否是質數,那就要算(19291220320323-1)!是多少

開始計算 19291220320323 X 19291220320323 X 19291220320322 ...........

可以想像,這個的計算量本身可能比確認他是不是質數還要困難....XD

因此對於數學家而言,用威爾斯定理(Wilson's theorem)去確認他們最新發現質數,並不是個實用的方法。

▌心得

  • 威爾斯定理(Wilson's theorem)是一個檢驗質數方法,但蠻不實用的
  • 所謂「定理」是對於現象的一種描述,但不代表他就會很有用。

上一篇
Day 24:[計算機概論]如果把加減乘除串起來用?——Toy Machine的ALU結構
下一篇
Day26:[離散數學]複雜度的數學證明
系列文
計算機概論X30天30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言